#include "atree.h"

/* **** Public Methods **** */

Atree::Atree()
{
 this->treeNode_ = 0; 
 this->resultRing_ = 0;
}

Atree::~Atree()
{
  this->destroyRecursively_(this->treeNode_);
}


void Atree::loadData(const char* filename)
{
  int commandValue;
  std::ifstream inputStream(filename);

  this->treeNode_ = new TreeNode;
  this->treeNode_->brotherNode = 0;
  this->treeNode_->childNode = 0;
  this->treeNode_->keyRing = 0;

  this->loadRecursively_(this->treeNode_, 0, inputStream);
  inputStream.close();
}

void Atree::saveData(const char* filename)
{
  std::ofstream outputStream(filename);
  this->saveRecursively_(this->treeNode_, outputStream);
  outputStream << "U\n";
  outputStream.close();
}

void Atree::insertData(const char* key_const, const char* data, bool ignoreCase)
{
  char* key = new char[std::strlen(key_const) + 1];
  std::strcpy(key, key_const);
  key[std::strlen(key_const)] = '\0';

  if (this->treeNode_ == 0)
  {
    this->treeNode_ = new TreeNode;
    this->treeNode_->brotherNode = 0;
    this->treeNode_->childNode = 0;
    this->treeNode_->keyRing = 0;
    this->treeNode_->nodeLabel = '\0';
  }
  TreeNode* treeNode = this->treeNode_;
  TreeNode* parentNode = treeNode;

  for ( ; key[0] != '\0'; key++)
  {
    if (ignoreCase)
    {
      if (key[0] >= 65 && key[0] <= 90)
      {
        key[0] += 32;
      }
    }

    TreeNode* previousNode = 0;
    bool bGoodFlag = false;

    if (treeNode->nodeLabel == '\0')
    {
      treeNode->nodeLabel = key[0];
      bGoodFlag = true;
    }

    while (!bGoodFlag)
    {
      if (treeNode->nodeLabel < key[0])
      {
        TreeNode* nodeA = previousNode;
        TreeNode* nodeB;
        TreeNode* nodeC = treeNode;

        if (previousNode != 0)
        {
          nodeA->brotherNode = new TreeNode;
          nodeB = nodeA->brotherNode;
          nodeB->brotherNode = nodeC;
          nodeB->childNode = 0;
          nodeB->nodeLabel = key[0];
          nodeB->keyRing = 0;

          treeNode = nodeB;
        }
        else
        {
          nodeB = treeNode;
          nodeA = new TreeNode;
          nodeA->brotherNode = nodeB;
          nodeA->childNode = 0;
          nodeA->nodeLabel = key[0];
          nodeA->keyRing = 0;

          if (nodeB == this->treeNode_)
          {
            this->treeNode_ = nodeA;
          }
          if (nodeB == parentNode->childNode)
          {
            parentNode->childNode = nodeA;
          }
              
          treeNode = nodeA;
        }
        bGoodFlag = true;
      }

      if (treeNode->nodeLabel == key[0])
      {
        bGoodFlag = true;
      }

      if (!bGoodFlag)
      {
        previousNode = treeNode;
        treeNode = treeNode->brotherNode;
      }

      if (treeNode == 0)
      {
        previousNode->brotherNode = new TreeNode;
        treeNode = previousNode->brotherNode;
        treeNode->brotherNode = 0;
        treeNode->childNode = 0;
        treeNode->nodeLabel = key[0];
        treeNode->keyRing = 0;
        bGoodFlag = true;
      }
    }

    if (treeNode->childNode == 0)
    {
      treeNode->childNode = new TreeNode;
      treeNode->childNode->brotherNode = 0;
      treeNode->childNode->childNode = 0;
      treeNode->childNode->keyRing = 0;
      treeNode->childNode->nodeLabel = '\0';
    }
    parentNode = treeNode;
    treeNode = treeNode->childNode;
  }
  if (parentNode->keyRing != 0)
  {
    KeyRing* cRing = parentNode->keyRing;
    while (cRing->nextRing != 0)
    {
      cRing = cRing->nextRing;
    }
    cRing->nextRing = new KeyRing;
    cRing = cRing->nextRing;
    cRing->key = new char[std::strlen(data) + 1];
    std::strcpy(cRing->key, data);
    cRing->nextRing = 0;
  }
  else
  {
   parentNode->keyRing = new KeyRing;
   parentNode->keyRing->key = new char[std::strlen(data) + 1];
   std::strcpy(parentNode->keyRing->key, data);
   parentNode->keyRing->nextRing = 0;
  }
}

void Atree::lookupData(const char* key, bool acceptPartial, bool ignoreCase)
{
  const char* key_first = key;
  TreeNode* treeNode = this->treeNode_;
  TreeNode* previousNode = treeNode;
  for ( ; key[0] != '\0'; key++)
  {
    bool bGoodFlag = false;
    while (!bGoodFlag)
    {
      previousNode = treeNode;
      if (treeNode==0) //If we run out of nodes, the search has of course, failed
      {
        this->resultRing_ = 0;
        return;
      }

      if (ignoreCase)
      {
        char cSearch = key[0], cTest = treeNode->nodeLabel;
        if (cSearch >= 65 && cSearch <=90) //Uppercase the letters
        {
          cSearch += 32;
        }
        if (cTest >= 65 && cTest <= 90) //Uppercase the letters
        {
          cTest += 32;
        }
        
        if (cTest == cSearch) //We have a hit!
        {
          bGoodFlag = true;
          treeNode = treeNode->childNode;
        }
      }
      else
      {
        if (key[0] == treeNode->nodeLabel)
        {
          bGoodFlag = true;
          treeNode = treeNode->childNode;
        }
      }
      if (!bGoodFlag)
      {
        treeNode = treeNode->brotherNode;
      }
    }
  }
  treeNode = previousNode;

  KeyRing* keyRing = treeNode->keyRing;
  this->resultRing_ = new ResultRing; 
  ResultRing* resultRing = this->resultRing_;
  resultRing->nextRing = 0;
  
  key = key_first;
  while (keyRing != 0)
  {
    resultRing->key = new char[std::strlen(key) + 1];
    std::strcpy(resultRing->key, key);

    resultRing->data = new char[std::strlen(keyRing->key) + 1];
    std::strcpy(resultRing->data, keyRing->key);

    resultRing->nextRing = new ResultRing;

    resultRing = resultRing->nextRing;

    resultRing->nextRing = 0;

    keyRing = keyRing->nextRing;
  }

  if (acceptPartial)
  {
    char* key_m1 = new char[std::strlen(key) + 1];
    std::strcpy(key_m1, key);
    key_m1[std::strlen(key) - 1] = '\0';
    this->searchRecursively_(treeNode->childNode, key);
    key_m1[std::strlen(key) - 1] = 'a';
    delete[] key_m1;
  }

  resultRing = this->resultRing_;
  ResultRing* previousResultRing = resultRing;

  while (resultRing->nextRing != 0)
  {
    previousResultRing = resultRing;
    resultRing = resultRing->nextRing;
  }

  if (resultRing==previousResultRing)
  {
    this->resultRing_ = 0;
  }
  else
  {
    previousResultRing->nextRing = 0;
  }
  
  if (resultRing != 0)
  {
    delete resultRing;
  }
}

bool Atree::hasData()
{
  if (this->resultRing_ != 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}

char* Atree::returnKey()
{
  char* tmpReturnKey = new char[std::strlen(this->resultRing_->key) + 1];
  std::strcpy(tmpReturnKey, this->resultRing_->key);
  return tmpReturnKey;
}

char* Atree::returnData()
{
  char* tmpReturnData = new char[std::strlen(this->resultRing_->data) + 1];
  std::strcpy(tmpReturnData, this->resultRing_->data);
  return tmpReturnData;
}

void Atree::moveNextData()
{
  ResultRing* previousRing = this->resultRing_;
  this->resultRing_ = this->resultRing_->nextRing;
  delete[] previousRing->key;
  delete[] previousRing->data;
  delete previousRing;
}
/* **** Private Methods **** */

void Atree::destroyRecursively_(TreeNode* treeNode)
{
  while (treeNode != 0)
  {
    /* Destroy the nodes children */
    this->destroyRecursively_(treeNode->childNode);
    
    /* Move on to the next node, and destroy the node we just processed */
    TreeNode* lastNode = treeNode;
    treeNode = treeNode->brotherNode;

    delete lastNode;
  }
}

void Atree::saveRecursively_(TreeNode* treeNode, std::ofstream& outputStream)
{
  char labelBuffer[2];
  labelBuffer[1] = '\0';

  while (treeNode != 0)
  {
    if (treeNode->childNode != 0)
    {
      outputStream << "R\n";
      this->saveRecursively_(treeNode->childNode, outputStream);
      outputStream << "U\n";
    }
      
    labelBuffer[0] = treeNode->nodeLabel;
    
    outputStream << "L\n" << labelBuffer << "\n";

    if (treeNode->keyRing != 0)
    {
      outputStream << "K\n";

      for (KeyRing* keyRing = treeNode->keyRing; keyRing != 0; keyRing = keyRing->nextRing)
      {
        outputStream << keyRing->key << "\n";
      }

      outputStream << ".\n";
    }

    outputStream << "B\n";

    treeNode = treeNode->brotherNode;
  }
}

void Atree::loadRecursively_(TreeNode* treeNode, TreeNode* parentNode, std::ifstream& inputStream)
{
  TreeNode* previousNode = treeNode;
  TreeNode* originalNode = treeNode;
  char commandBuffer[2];
  commandBuffer[1] = '\0';
  while (true)
  {
    inputStream.getline(commandBuffer, 2);

    if (commandBuffer[0]=='R')
    {
      treeNode->childNode = new TreeNode;
      treeNode->childNode->brotherNode = 0;
      treeNode->childNode->childNode = 0;
      treeNode->childNode->keyRing = 0;

      this->loadRecursively_(treeNode->childNode, treeNode, inputStream);
    }

    if (commandBuffer[0]=='U')
    {
      if (originalNode==treeNode && parentNode != 0)
      {
        parentNode->childNode = 0;
      }

      delete treeNode;

      if (previousNode != 0)
      {
        previousNode->brotherNode = 0;
      }
      return;
    }
  
    if (commandBuffer[0]=='B')
    {
      treeNode->brotherNode = new TreeNode;
      treeNode->brotherNode->brotherNode = 0;
      treeNode->brotherNode->childNode = 0;
      treeNode->brotherNode->keyRing = 0;

      previousNode = treeNode;

      treeNode = treeNode->brotherNode;
    }

    if (commandBuffer[0]=='L')
    {
      char keyBuffer[2];
      keyBuffer[1] = '\0';

      inputStream.getline(keyBuffer,2);
      treeNode->nodeLabel = keyBuffer[0];
    }

    if (commandBuffer[0]=='K')
    {
      KeyRing* previousKeyRing;
      KeyRing* keyRing;

      treeNode->keyRing = new KeyRing;
      keyRing = treeNode->keyRing;
      
      char dataBuffer[MAX_DATA_LENGTH + 1];
      dataBuffer[0] = '\0';

      inputStream.getline(dataBuffer, MAX_DATA_LENGTH);
      while (dataBuffer[0] != '.' || dataBuffer[1] != '\0')
      {

        keyRing->key = new char[std::strlen(dataBuffer) + 1];
        std::strcpy(keyRing->key, dataBuffer);

        keyRing->nextRing = new KeyRing;
        previousKeyRing = keyRing;
        
        keyRing = keyRing->nextRing;
        inputStream.getline(dataBuffer, MAX_DATA_LENGTH);
      }
      delete keyRing;
      if (previousKeyRing != 0)
      {
        previousKeyRing->nextRing = 0;
      }
    }
  }
}

void Atree::searchRecursively_(TreeNode* treeNode, const char* previousKey)
{
  char* keyLabel = new char[std::strlen(previousKey) + 2];
  std::strcpy(keyLabel, previousKey);
  keyLabel[std::strlen(previousKey) + 1] = '\0';

  while (treeNode != 0)
  {
    keyLabel[std::strlen(previousKey) + 0] = treeNode->nodeLabel;

    this->searchRecursively_(treeNode->childNode, keyLabel);
    
    ResultRing* resultRing = this->resultRing_;
    while (resultRing->nextRing != 0)
    {
      resultRing = resultRing->nextRing;
    }
    
    KeyRing* keyRing = treeNode->keyRing;
    while (keyRing != 0)
    {
      resultRing->key = new char[std::strlen(keyLabel) + 1];
      std::strcpy(resultRing->key, keyLabel);
      resultRing->data = new char[std::strlen(keyRing->key) + 1];
      std::strcpy(resultRing->data, keyRing->key);
      resultRing->nextRing = new ResultRing;
      resultRing = resultRing->nextRing;
      resultRing->nextRing = 0;

      keyRing = keyRing->nextRing;
    }
    treeNode = treeNode->brotherNode;
  }
}
